The present invention relates to the field of message passing algorithms for performing inference on graphical models. Such message passing algorithms are employed in the field of error correction coding and decoding. Thus, the present invention relates also to the field of error correction coding and decoding and, more particularly, to Low Density Parity Check (LDPC) codes and to an LDPC decoder.
The process of transmitting digital data can introduce errors into the data. As a result, the received data can be different from the transmitted data. Such errors are typically caused by noise that is present in the transmission channel. The amount of errors is generally related to the transmission signal strength in relation to the amount of noise present. Error correction coding is a technique by which redundancy is inserted into the data prior to transmission. Upon reception, this redundancy is used in an attempt to correct errors that were introduced during the transmission process.
Block coding is a type of error correction coding in which the digital data to be transmitted is broken into messages of fixed size. Prior to transmission, each message is encoded into a codeword (also referred to as a “block”) by an encoder. Redundancy is inserted during the encoding process so that the codewords are made larger than the messages. Assume that the codewords each consist of n bits. Only certain patterns of n bits are codewords; the remaining patterns are invalid. The codewords are then transmitted, which may cause the codewords to become corrupted. Upon reception, a decoder attempts to infer the original messages from the received, and possibly corrupted, codewords.
A linear block error correction code is one in which any linear combination of codewords is also a codeword. A generator matrix can be used during the encoding process to encode the messages into valid codewords. Upon reception, a parity check matrix can be used during the decoding process to generate an error vector, where the error vector indicates the presence of errors in the received codeword. The parity check matrix is related to the generator matrix in that it can be derived from the generator matrix.
Low Density Parity Check (LDPC) codes are a subcategory of linear block error correction codes characterized by a sparse parity check matrix. This means that the parity check matrix consists mainly of 0's and a relatively small number of 1's.
LDPC codes were first introduced in the 1960's but have more recently received increased attention. This is due at least in part to inherent parallelism in decoding which makes LDPC codes suitable for hardware implementation and due to flexibility in designing LDPC codes, which allows LDPC codes to be used in a variety of applications.
An LDPC code is a linear error-correction code, fully defined by a sparse binary parity check matrix H. A bipartite Tanner graph is a widely used way to represent a parity check matrix H. This graph consists of two sets of nodes, namely the check nodes and the variable nodes. Each row of H corresponds to a parity check equation, graphically represented as a check node of the Tanner graph, while columns correspond to the codeword bits, graphically represented as variable nodes. An ace in the H matrix indicates a connection between the corresponding variable and check nodes. Message passing algorithms for decoding LDPC codes operate by iteratively passing information along the edges of the Tanner graph. In a sense, the variable nodes correspond to bits of a received word, both message and parity, while check nodes correspond to parity check equations.
Decoding of LDPC codes can be based on sum-product message passing, which is also referred to as a belief propagation. In this case, the Tanner graph for a particular LDPC code can be used as a guide for constructing a hardware decoder for the code by replacing the nodes of the Tanner graph with computing elements and by replacing the edges between the nodes with communication buses that connect the computing elements. Probabilistic information, in the form of log-likelihood ratios (LLRs), can be passed along the communication buses between the computing elements.
While sum-product message passing (or belief propagation) is considered to be near-optimal for LDPC codes, practical LDPC decoders must take into account considerations such as decoder size and latency. This is particularly the case for LDPC codes whose codeword lengths can be, for example, 648, 1296, or 1944 bits, or longer. Thus, in an effort to reduce complexity, hardware decoders commonly use an approximation of the sum-product algorithm, such as the min-sum algorithm and its variations (e.g. normalized min-sum, offset min-sum, corrected min-sum, etc).
An operation that is typically performed within the node processors of an error correction decoder that employs message passing based on the min-sum algorithm and its variations involves identifying the two minimum values from a greater number of inputs. Existing methods of identifying the two minimum values tend to require circuitry having complexity that is relatively high, in terms of hardware, latency, and power dissipation.